{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Linked List in Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #linked-list #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #链表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSubPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中的链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵以&nbsp;<code>root</code>&nbsp;为根的二叉树和一个&nbsp;<code>head</code>&nbsp;为第一个节点的链表。</p>\n",
    "\n",
    "<p>如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以&nbsp;<code>head</code>&nbsp;为首的链表中每个节点的值，那么请你返回 <code>True</code> ，否则返回 <code>False</code> 。</p>\n",
    "\n",
    "<p>一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/29/sample_1_1720.png\" style=\"height: 280px; width: 220px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>树中蓝色的节点构成了与链表对应的子路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/29/sample_2_1720.png\" style=\"height: 280px; width: 220px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>二叉树中不存在一一对应链表的路径。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树和链表中的每个节点的值都满足&nbsp;<code>1 &lt;= node.val&nbsp;&lt;= 100</code>&nbsp;。</li>\n",
    "\t<li>链表包含的节点数目在&nbsp;<code>1</code>&nbsp;到&nbsp;<code>100</code>&nbsp;之间。</li>\n",
    "\t<li>二叉树包含的节点数目在&nbsp;<code>1</code>&nbsp;到&nbsp;<code>2500</code>&nbsp;之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [linked-list-in-binary-tree](https://leetcode.cn/problems/linked-list-in-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [linked-list-in-binary-tree](https://leetcode.cn/problems/linked-list-in-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,8]\\n[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]', '[1,4,2,6]\\n[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]', '[1,4,2,6,8]\\n[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "            \n",
    "        def check(root, head):\n",
    "            if not head: return True\n",
    "            if not root or root.val != head.val :\n",
    "                return False\n",
    "            return check(root.left, head.next) or check(root.right, head.next) \n",
    "\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.val == head.val and check(node, head):\n",
    "                    return True\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        \n",
    "        return False\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def judge(head, root):\n",
    "            nonlocal res\n",
    "            state1 = head\n",
    "            state2 = [root]\n",
    "            while state1 != None and len(state2) > 0:\n",
    "                temp2 = []\n",
    "                for node in state2:\n",
    "                    if node.left != None and state1.next != None and node.left.val == state1.next.val:\n",
    "                        temp2.append(node.left)\n",
    "                    if node.right != None and state1.next != None and node.right.val == state1.next.val:\n",
    "                        temp2.append(node.right)\n",
    "                state2 = temp2\n",
    "                state1 = state1.next\n",
    "            if state1 == None:\n",
    "                res = True\n",
    "        \n",
    "        res = False\n",
    "        state = [root]\n",
    "        while len(state) > 0:\n",
    "            temp = []\n",
    "            for node in state:\n",
    "                if node.val == head.val:\n",
    "                    judge(head, node)\n",
    "                \n",
    "                if node.left != None:\n",
    "                    temp.append(node.left)\n",
    "                if node.right != None:\n",
    "                    temp.append(node.right)\n",
    "            state = temp\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root,cur_listNode):\n",
    "            if not cur_listNode:\n",
    "                return True\n",
    "            \n",
    "            if not root or root.val != cur_listNode.val:\n",
    "                return False\n",
    "            \n",
    "            return dfs(root.left,cur_listNode.next) or dfs(root.right,cur_listNode.next)\n",
    "\n",
    "        from collections import deque\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            cur_node = stack.popleft()\n",
    "            if cur_node.val == head.val and dfs(cur_node,head):\n",
    "                return True\n",
    "            if cur_node.left:\n",
    "                stack.append(cur_node.left)\n",
    "            if cur_node.right:\n",
    "                stack.append(cur_node.right)\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.headlist = []\n",
    "    \n",
    "    def dfsGetHeadList(self, node: TreeNode, head: ListNode):\n",
    "        if not node:\n",
    "            return\n",
    "        if node.val == head.val:\n",
    "            self.headlist.append(node)\n",
    "        self.dfsGetHeadList(node.left, head)\n",
    "        self.dfsGetHeadList(node.right, head)\n",
    "\n",
    "    def dfsCheckList(self, node: TreeNode, head:ListNode):\n",
    "        if head is None:\n",
    "            return True\n",
    "\n",
    "        if head and not node:\n",
    "            return False\n",
    "        if head and node and node.val != head.val:\n",
    "            return False\n",
    "\n",
    "        left = self.dfsCheckList(node.left, head.next)\n",
    "        right = self.dfsCheckList(node.right, head.next)\n",
    "\n",
    "        if (left or right):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        result = False\n",
    "        self.dfsGetHeadList(root, head)\n",
    "        for node in self.headlist:\n",
    "            result = self.dfsCheckList(node, head)\n",
    "            if result:\n",
    "                return result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        sub_str = ''\n",
    "        node = head\n",
    "        while node != None:\n",
    "            sub_str += str(node.val) + ' '\n",
    "            node = node.next\n",
    "        sub_str.strip()\n",
    "\n",
    "        answer = False\n",
    "\n",
    "        if root != None:\n",
    "            stack = [[root, '']]\n",
    "            while stack and answer == False:\n",
    "                _list = []\n",
    "                for node,path in stack:\n",
    "                    np = path[:]\n",
    "                    np += str(node.val) + ' '\n",
    "                    if node.left == None and node.right == None:\n",
    "                        np.strip()\n",
    "                        if np.find(sub_str) != -1:\n",
    "                            answer = True\n",
    "                            break\n",
    "                    if node.left != None:\n",
    "                        _list.append([node.left, np])\n",
    "                    if node.right != None:\n",
    "                        _list.append([node.right, np])\n",
    "                stack[:] = _list[:]\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def check_node(root, cur_listNode):\n",
    "            if not cur_listNode:\n",
    "                return True\n",
    "            if not root or root.val != cur_listNode.val:\n",
    "                return False\n",
    "            return check_node(root.left, cur_listNode.next) or check_node(root.right, cur_listNode.next)\n",
    "\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            cur_node = stack.popleft()\n",
    "            if cur_node.val == head.val and check_node(cur_node, head):\n",
    "                return True\n",
    "            if cur_node.left: stack.append(cur_node.left)\n",
    "            if cur_node.right: stack.append(cur_node.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, cur_head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if root == None and cur_head != None:\n",
    "            return False\n",
    "        if cur_head == None:\n",
    "            return True\n",
    "        if cur_head.val == root.val:\n",
    "            return self.dfs(cur_head.next, root.left) or self.dfs(cur_head.next, root.right)\n",
    "\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        q = [root]\n",
    "        while len(q) > 0:\n",
    "            x = q.pop(0)\n",
    "            if x.left != None:\n",
    "                q.append(x.left)\n",
    "            if x.right != None:\n",
    "                q.append(x.right)\n",
    "            if(self.dfs(head, x)):\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        sub_str = ''\n",
    "        node = head\n",
    "        while node != None:\n",
    "            sub_str += str(node.val) + ' '\n",
    "            node = node.next\n",
    "        sub_str.strip()\n",
    "\n",
    "        answer = False\n",
    "\n",
    "        if root != None:\n",
    "            stack = [[root, '']]\n",
    "            while stack and answer == False:\n",
    "                _list = []\n",
    "                for node,path in stack:\n",
    "                    np = path[:]\n",
    "                    np += str(node.val) + ' '\n",
    "                    if node.left == None and node.right == None:\n",
    "                        np.strip()\n",
    "                        if np.find(sub_str) != -1:\n",
    "                            answer = True\n",
    "                            break\n",
    "                    if node.left != None:\n",
    "                        _list.append([node.left, np])\n",
    "                    if node.right != None:\n",
    "                        _list.append([node.right, np])\n",
    "                stack[:] = _list[:]\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        sub_str = ''\n",
    "        node = head\n",
    "        while node != None:\n",
    "            sub_str += str(node.val) + ' '\n",
    "            node = node.next\n",
    "        sub_str.strip()\n",
    "\n",
    "        answer = False\n",
    "\n",
    "        if root != None:\n",
    "            stack = [[root, '']]\n",
    "            while stack and answer == False:\n",
    "                _list = []\n",
    "                for node,path in stack:\n",
    "                    np = path[:]\n",
    "                    np += str(node.val) + ' '\n",
    "                    if node.left == None and node.right == None:\n",
    "                        np.strip()\n",
    "                        if np.find(sub_str) != -1:\n",
    "                            answer = True\n",
    "                            break\n",
    "                    if node.left != None:\n",
    "                        _list.append([node.left, np])\n",
    "                    if node.right != None:\n",
    "                        _list.append([node.right, np])\n",
    "                stack[:] = _list[:]\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            node = queue.pop()\n",
    "            if self.dfs(node, head):\n",
    "                return True\n",
    "            if node.left:\n",
    "                queue.appendleft(node.left)\n",
    "            if node.right:\n",
    "                queue.appendleft(node.right)\n",
    "        return False\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], pointer: Optional[ListNode]):\n",
    "        if node.val == pointer.val:\n",
    "            if not pointer.next:\n",
    "                return True\n",
    "            ans = []\n",
    "            if node.left:\n",
    "                ans.append(self.dfs(node.left, pointer.next))\n",
    "            if node.right:\n",
    "                ans.append(self.dfs(node.right, pointer.next))\n",
    "            return any(ans)\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "            \n",
    "        def check(root, head):\n",
    "            if not head: \n",
    "                return True\n",
    "            if not root or root.val != head.val :\n",
    "                return False\n",
    "            return check(root.left, head.next) or check(root.right, head.next) \n",
    "\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if check(node, head):\n",
    "                    return True\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if self.search(head, node):\n",
    "                return True\n",
    "\n",
    "            if node.left is not None:\n",
    "                queue.append(node.left)\n",
    "            if node.right is not None:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        return False\n",
    "\n",
    "    def search(self,  head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        queue = deque()\n",
    "        queue.append((head, root))\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            match queue.popleft():\n",
    "                case (None, _): return True\n",
    "                case (expect, None): pass\n",
    "                case (expect, actual) if expect.val != actual.val: pass\n",
    "                case (expect, actual):\n",
    "                    queue.append((expect.next, actual.left))\n",
    "                    queue.append((expect.next, actual.right))\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "            \n",
    "        def check(root, head):\n",
    "            if not head: \n",
    "                return True\n",
    "            if not root or root.val != head.val :\n",
    "                return False\n",
    "            return check(root.left, head.next) or check(root.right, head.next) \n",
    "\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.val == head.val and check(node, head):\n",
    "                    return True\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, head: ListNode, rt: TreeNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not rt:\n",
    "            return False\n",
    "        if rt.val != head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, rt.left) or self.dfs(head.next, rt.right)\n",
    "\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        self.head = head\n",
    "        self.root = root\n",
    "        self.res = False\n",
    "        self.pre(root)\n",
    "        return self.res\n",
    "    def pre(self,node):\n",
    "        if not node:\n",
    "            return \n",
    "        else:\n",
    "            temp = self.head\n",
    "            if self.check(node,temp):\n",
    "                self.res = True\n",
    "                return\n",
    "            self.pre(node.left)\n",
    "            self.pre(node.right)\n",
    "            return \n",
    "    def check(self,node,Node):\n",
    "        if not Node:\n",
    "            return True\n",
    "        if not node:\n",
    "            return False\n",
    "        else:\n",
    "            if node.val == Node.val:\n",
    "                return self.check(node.left,Node.next) or self.check(node.right,Node.next)\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def helper(self,head,root):\n",
    "        if not head:\n",
    "            return True \n",
    "        if not root:\n",
    "            return False\n",
    "        if not head and not root:\n",
    "            return False   \n",
    "        # if root and root.val !=head.val or not root:\n",
    "        #     return False \n",
    "        return head.val==root.val and (self.helper(head.next,root.left) or self.helper(head.next,root.right))\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.helper(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, head, root):\n",
    "        if not head:\n",
    "            return True \n",
    "        if not root:\n",
    "            return False \n",
    "        if head.val != root.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:        \n",
    "        if not root:\n",
    "            return not head \n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def helper(self,head,root):\n",
    "        if not head:return True \n",
    "        if root and root.val !=head.val or not root:return False \n",
    "        return head.val==root.val and (self.helper(head.next,root.left) or self.helper(head.next,root.right))\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:return False\n",
    "        return self.helper(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, head: ListNode, root: TreeNode):\n",
    "        if head is None:\n",
    "            return True\n",
    "        if root is None:\n",
    "            return False\n",
    "        if head.val != root.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)\n",
    "    \n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 数字会重复，不可行\n",
    "        # dp = [[0 for _ in range(101)] for _ in range(101)]\n",
    "        # q = deque()\n",
    "        # q.append(root)\n",
    "        # while len(q):\n",
    "        #     node = q.pop()\n",
    "        #     dp[0][node.val] = 1\n",
    "        #     if node.left is not None:\n",
    "        #         q.append(node.left)\n",
    "        #         dp[node.val][node.left.val] = 1\n",
    "        #     if node.right is not None:\n",
    "        #         q.append(node.right)\n",
    "        #         dp[node.val][node.right.val] = 1\n",
    "        # lnode, rnode = None, head\n",
    "        # while rnode is not None:\n",
    "        #     lv, rv = 0 if lnode == None else lnode.val, rnode.val\n",
    "        #     if dp[lv][rv] != 1:\n",
    "        #         return False\n",
    "        #     lnode = rnode\n",
    "        #     rnode = rnode.next\n",
    "        # return True\n",
    "\n",
    "        # 纯dfs\n",
    "        if root is None:\n",
    "            return False\n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if head is None:\n",
    "            return True\n",
    "        if root is None:\n",
    "            return False\n",
    "        return rec(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n",
    "\n",
    "\n",
    "def rec(head, root):\n",
    "    if head is None:\n",
    "        return True\n",
    "    if root is None or head.val != root.val:\n",
    "        return False\n",
    "    return rec(head.next, root.left) or rec(head.next, root.right)\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        self.a=[]\n",
    "        self.b=[]\n",
    "        p=head\n",
    "        while p:\n",
    "            self.a.append(p.val)\n",
    "            p=p.next\n",
    "        self.res=False\n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return\n",
    "            self.b.append(r.val)\n",
    "            if len(self.b)>=len(self.a) and self.b[-len(self.a):]==self.a:\n",
    "                self.res=True\n",
    "            dfs(r.left)\n",
    "            dfs(r.right)\n",
    "            self.b.pop()\n",
    "\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,head,root):\n",
    "        if not head:\n",
    "            return True\n",
    "        if not root:\n",
    "            return False\n",
    "        if head.val != root.val:\n",
    "            return False\n",
    "        return self.dfs(head.next,root.left) or self.dfs(head.next,root.right)\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def helper(self,head,root):\n",
    "        if not head:return True \n",
    "        if root and root.val !=head.val or not root:return False \n",
    "        return head.val==root.val and self.helper(head.next,root.left) or self.helper(head.next,root.right)\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:return False\n",
    "        return self.helper(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "        def dfs(self, head: Optional[ListNode], rt: Optional[TreeNode]) -> bool:\n",
    "                if not head:\n",
    "                    return True\n",
    "                if not rt:\n",
    "                    return False\n",
    "                if rt.val != head.val:\n",
    "                    return False\n",
    "                return self.dfs(head.next, rt.left) or self.dfs(head.next, rt.right)\n",
    "            \n",
    "        def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "            if not root:\n",
    "                return False\n",
    "            return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head,root) or self.isSubPath(head, root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "    def dfs(self, head, root):\n",
    "        if not head:\n",
    "            return True\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val != head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        if not head: return True\n",
    "        if not root: return False\n",
    "        def isMatch(root,head):\n",
    "            if not head: return True\n",
    "            if not root: return False\n",
    "            if root.val != head.val: return False\n",
    "            return isMatch(root.left,head.next) or isMatch(root.right,head.next)\n",
    "        return isMatch(root,head) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "#         if head is None:\n",
    "#             return True\n",
    "#         if root is None:\n",
    "#             return False\n",
    "#         cur_result = False\n",
    "#         left_result = False\n",
    "#         right_result = False\n",
    "#         if head.val == root.val:\n",
    "#             cur_result = self.isSubPath(head.next, root.left) or self.isSubPath(head.next, root.right)\n",
    "#         if root.left is not None:\n",
    "#             left_result = self.isSubPath(head, root.left)\n",
    "#         if root.right is not None:\n",
    "#             right_result = self.isSubPath(head, root.right)\n",
    "\n",
    "#         return cur_result or left_result or right_result\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, head: ListNode, rt: TreeNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not rt:\n",
    "            return False\n",
    "        if rt.val != head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, rt.left) or self.dfs(head.next, rt.right)\n",
    "\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 两重DFS\n",
    "        def dfs(head, root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val != head.val:\n",
    "                return False\n",
    "            if dfs(head.next, root.left) or dfs(head.next, root.right):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        if dfs(head, root):\n",
    "            return True\n",
    "        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 1.DFS找到与head头节点值相同的所有节点, 存储在starts中\n",
    "        # 2.遍历starts中每个节点，然后DFS查找一条满足条件的路径\n",
    "\n",
    "        starts: List[TreeNode] = []\n",
    "        \n",
    "        def dfs(root: Optional[TreeNode]) -> None:\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val == head.val:\n",
    "                starts.append(root)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "\n",
    "        return any([self.find_path(start, head) for start in starts])\n",
    "\n",
    "    def find_path(self, root: TreeNode, head: ListNode) -> bool:\n",
    "        # DFS查找路径\n",
    "        if not root and head:\n",
    "            return False\n",
    "        elif not head:\n",
    "            return True\n",
    "        \n",
    "        left = self.find_path(root.left, head.next)\n",
    "        right = self.find_path(root.right, head.next)\n",
    "\n",
    "        return root.val == head.val and (left or right)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def isMatch(root,head):\n",
    "            if not head: return True\n",
    "            if not root: return False\n",
    "            if head.val != root.val: return False\n",
    "            return isMatch(root.left,head.next) or isMatch(root.right,head.next)\n",
    "        if not head: return True\n",
    "        if not root: return False\n",
    "        if isMatch(root,head): return True\n",
    "        return self.isSubPath(head,root.left) or self.isSubPath(head,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(r):\n",
    "            res = []\n",
    "            if r is None:\n",
    "                return []\n",
    "            res.append(r)\n",
    "            res += dfs(r.left)\n",
    "            res += dfs(r.right)\n",
    "            return res\n",
    "\n",
    "        def isSub(h,r):\n",
    "            \n",
    "            if h is None:\n",
    "                return True\n",
    "            else:\n",
    "                if r is None:\n",
    "                    return False \n",
    "                elif h.val != r.val:\n",
    "                    return False\n",
    "                else:\n",
    "                    return (isSub(h.next,r.left) or isSub(h.next,r.right))\n",
    "            \n",
    "        queue = dfs(root)\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(len(queue)):\n",
    "            if isSub(head,queue[i]):\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root or not head: return False\n",
    "        def check(node_tree, node_list):\n",
    "            if not node_list: return True\n",
    "            if not node_tree: return False\n",
    "            if node_list.val!=node_tree.val: return False\n",
    "            return check(node_tree.left, node_list.next) or check(node_tree.right, node_list.next)\n",
    "        return check(root,head) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return False\n",
    "        def dfs(node, root):\n",
    "            if not node: return True\n",
    "            if not root: return False\n",
    "            if node.val == root.val:\n",
    "                return dfs(node.next, root.left) or dfs(node.next, root.right)\n",
    "        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        def dfs(head,root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val!=head.val:\n",
    "                return False\n",
    "            return dfs(head.next,root.left) or dfs(head.next,root.right)\n",
    "        return dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "        # #每一条走到叶子节点的路径，然后发现一致就true\n",
    "        # cur = head\n",
    "        # def dfs(node,cur):\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     if node == cur:\n",
    "        #         if node.left:\n",
    "        #             dfs(node.left,cur.next)\n",
    "        #         if node.right:\n",
    "        #             dfs(node.right,cur.next)\n",
    "        #         if not cur:\n",
    "        #             return True\n",
    "        #     if node.left:\n",
    "        #         dfs(node.left,cur)\n",
    "        #     if node.right:\n",
    "        #         dfs(node.right,cur)\n",
    "        # return False            \n",
    "        \n",
    "        # return dfs(root,cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def find(head: Optional[ListNode], root: Optional[TreeNode]):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "            if head.val != root.val:\n",
    "                return False\n",
    "            return find(head.next, root.left) or find(head.next, root.right)\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        if head.val == root.val:\n",
    "            if find(head.next, root.left) or find(head.next, root.right):\n",
    "                return True\n",
    "        return  find(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        def dfs(head,root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val!=head.val:\n",
    "                return False\n",
    "            return dfs(head.next,root.left) or dfs(head.next,root.right)\n",
    "        return dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "        # #每一条走到叶子节点的路径，然后发现一致就true\n",
    "        # cur = head\n",
    "        # def dfs(node,cur):\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     if node == cur:\n",
    "        #         if node.left:\n",
    "        #             dfs(node.left,cur.next)\n",
    "        #         if node.right:\n",
    "        #             dfs(node.right,cur.next)\n",
    "        #         if not cur:\n",
    "        #             return True\n",
    "        #     if node.left:\n",
    "        #         dfs(node.left,cur)\n",
    "        #     if node.right:\n",
    "        #         dfs(node.right,cur)\n",
    "        # return False            \n",
    "        \n",
    "        # return dfs(root,cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # find candidates root first\n",
    "        candidates=[]\n",
    "        def find_candidates(node):\n",
    "            #traverse, find root.val==head.val as candidates\n",
    "            if not node:return\n",
    "            if node.val==head.val:candidates.append(node)\n",
    "            find_candidates(node.left)\n",
    "            find_candidates(node.right)\n",
    "        find_candidates(root)\n",
    "        if not candidates:return False# if no root==head\n",
    "        \n",
    "        # check if subtree root contain sublist head\n",
    "        def check(root,head):\n",
    "            if not head:return True#if checked all list\n",
    "            elif not root:return False#if head but not root\n",
    "            \n",
    "            if root.val!=head.val:\n",
    "                return False\n",
    "            elif root.val==head.val:\n",
    "                #if root==head, check subtree with sublist\n",
    "                return check(root.left,head.next) or check(root.right,head.next)\n",
    "        for node in candidates:\n",
    "            if check(node,head):return True\n",
    "        else:return False#if checked all candidates\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        def dfs(tree_node, stack_node):\n",
    "            if not tree_node and not stack_node:\n",
    "                return True\n",
    "            if not tree_node and stack_node:\n",
    "                return False\n",
    "            if tree_node and not stack_node:\n",
    "                # print('tree_node and not stack_node')\n",
    "                return True\n",
    "            if tree_node.val != stack_node.val:\n",
    "                return False\n",
    "            else:\n",
    "                return dfs(tree_node.left, stack_node.next) or dfs(tree_node.right, stack_node.next)\n",
    "        return dfs(root, head) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def dfs(i: ListNode, j: TreeNode) -> bool:\n",
    "            if not i:\n",
    "                return True\n",
    "            \n",
    "            if not j:\n",
    "                return False\n",
    "            \n",
    "            if i.val != j.val:\n",
    "                return False\n",
    "\n",
    "            return dfs(i.next, j.left) or dfs(i.next, j.right)\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def traverse(head,root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "            return head.val==root.val and (traverse(head.next,root.left) or traverse(head.next,root.right))\n",
    "        \n",
    "\n",
    "        @lru_cache\n",
    "        def helper(head,root):\n",
    "            if not root:\n",
    "                return False\n",
    "            return traverse(head,root) or helper(head,root.left) or helper(head,root.right)\n",
    "            \n",
    "        \n",
    "        # @lru_cache\n",
    "        # def helper(head,root,started):\n",
    "        #     if not head:\n",
    "        #         return True\n",
    "        #     if not root:\n",
    "        #         return False\n",
    "        #     if started:\n",
    "        #         return root.val==head.val\n",
    "        #     if root.val==head.val and (helper(head.next,root.left,True) or\n",
    "        #         helper(head.next,root.right,True)):\n",
    "        #         return True\n",
    "        #     return helper(head,root.left,False) or helper(head,root.right,False)\n",
    "        return helper(head,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        def subpath(head:ListNode,rt:ListNode):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not rt:\n",
    "                return False\n",
    "            if head.val != rt.val:\n",
    "                return False\n",
    "            return subpath(head.next,rt.left) or subpath(head.next,rt.right)\n",
    "        if not root:\n",
    "            return False\n",
    "        return subpath(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        ptn = []\n",
    "        while head:\n",
    "            ptn.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        pi, j = [0] * (m := len(ptn)), 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and ptn[i] != ptn[j]: j = pi[j - 1]\n",
    "            pi[i] = (j := j + 1) if ptn[i] == ptn[j] else j\n",
    "        \n",
    "        @cache\n",
    "        def dfs_kmp(node, j):\n",
    "            if j == m: return True\n",
    "            if node is None: return False\n",
    "\n",
    "            while j > 0 and node.val != ptn[j]: j = pi[j - 1]\n",
    "            delta = int(node.val == ptn[j])\n",
    "            return dfs_kmp(node.left, j + delta) or dfs_kmp(node.right, j + delta)\n",
    "\n",
    "        return dfs_kmp(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def dfs(head, root):\n",
    "            if not root:\n",
    "                return False\n",
    "            \n",
    "            if root.val != head.val:\n",
    "                return False\n",
    "            if root.val == head.val and head.next != None:\n",
    "                head = head.next \n",
    "            elif root.val == head.val and head.next == None:\n",
    "                return True\n",
    "            \n",
    "            is_left = dfs(head, root.left)\n",
    "            is_right = dfs(head, root.right)\n",
    "            return is_left or is_right\n",
    "        \n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val == head.val:\n",
    "            is_find = dfs(head, root)\n",
    "            if is_find:\n",
    "                return True \n",
    "        l = self.isSubPath(head, root.left)\n",
    "        r = self.isSubPath(head, root.right)\n",
    "        return l or r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def dfs(head, root):\n",
    "            if not root:\n",
    "                return False\n",
    "            \n",
    "            if root.val != head.val:\n",
    "                return False\n",
    "            if root.val == head.val and head.next != None:\n",
    "                head = head.next \n",
    "            elif root.val == head.val and head.next == None:\n",
    "                return True\n",
    "            \n",
    "            is_left = dfs(head, root.left)\n",
    "            is_right = dfs(head, root.right)\n",
    "            return is_left or is_right\n",
    "        \n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val == head.val:\n",
    "            is_find = dfs(head, root)\n",
    "            if is_find:\n",
    "                return True \n",
    "        l = self.isSubPath(head, root.left)\n",
    "        r = self.isSubPath(head, root.right)\n",
    "        return l or r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def _isSubPath(head, root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "\n",
    "            if head.val != root.val:\n",
    "                return False\n",
    "\n",
    "            return _isSubPath(head.next, root.left) or _isSubPath(head.next, root.right)\n",
    "\n",
    "        def dfs(head, root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "\n",
    "            return (\n",
    "                _isSubPath(head, root) or dfs(head, root.left) or dfs(head, root.right)\n",
    "            )\n",
    "\n",
    "        return dfs(head, root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, head: ListNode, rt: TreeNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not rt:\n",
    "            return False\n",
    "        if rt.val != head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, rt.left) or self.dfs(head.next, rt.right)\n",
    "\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        if head == None:\n",
    "            return True\n",
    "        if root == None:\n",
    "            return False\n",
    "        # judge root, then judge root.left and root.right\n",
    "        return self.isSub(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "    \n",
    "    def isSub(self, head, node):\n",
    "        # list is over\n",
    "        if head == None:\n",
    "            return True\n",
    "        # list is not over and tree is over\n",
    "        if node == None:\n",
    "            return False\n",
    "        # not equal\n",
    "        if not head.val == node.val:\n",
    "            return False\n",
    "        # equal, then left and right\n",
    "        return self.isSub(head.next, node.left) or self.isSub(head.next, node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, head: ListNode, rt: TreeNode) -> bool:\n",
    "        if head is None:\n",
    "            return True\n",
    "        if rt is None:\n",
    "            return False\n",
    "        if rt.val != head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, rt.left) or self.dfs(head.next, rt.right)\n",
    "\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(head_cut,node):\n",
    "            if node is None:\n",
    "                return False\n",
    "            if head_cut.val!=node.val:\n",
    "                return False\n",
    "            head_cut=head_cut.next\n",
    "            if head_cut is None:\n",
    "                return True\n",
    "            else:\n",
    "                return dfs(head_cut,node.left) or dfs(head_cut,node.right)\n",
    "\n",
    "        def dfs_2(head,node):\n",
    "            if dfs(head,node):\n",
    "                return True\n",
    "            if node.left:\n",
    "                if dfs_2(head,node.left):\n",
    "                    return True\n",
    "            if node.right:\n",
    "                if dfs_2(head,node.right):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs_2(head,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "    \n",
    "    def dfs(self, head, node):\n",
    "        if not head:  # 链表已经全部匹配完，匹配成功\n",
    "            return True\n",
    "        if not node:\n",
    "            return False\n",
    "        if head.val != node.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, node.left) or self.dfs(head.next, node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 暴力解法，极有可能超时\n",
    "        def search(tree, chain):\n",
    "            if not chain:\n",
    "                return True\n",
    "            if not tree or tree.val != chain.val:\n",
    "                return False\n",
    "            return search(tree.left, chain.next) or search(tree.right, chain.next)\n",
    "        \n",
    "        # 先深搜获得深度，再广搜暴力找答案\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(dfs(node.left), dfs(node.right)) + 1\n",
    "        depth = dfs(root) + 1\n",
    "        # 找找链表的深度\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            depth -= 1\n",
    "            # 没链表深，直接返回\n",
    "            if depth < 0:\n",
    "                return False\n",
    "        # 此时的depth==树深度-链表深度，超过这个深度后，不能出现链表的头节点\n",
    "        \n",
    "\n",
    "        # 开始广搜\n",
    "        q = [root]\n",
    "        for _ in range(depth):\n",
    "            new = []\n",
    "            for node in q:\n",
    "                if search(node, head):\n",
    "                    return True\n",
    "                if node.left:\n",
    "                    new.append(node.left)\n",
    "                if node.right:\n",
    "                    new.append(node.right)\n",
    "            q = new\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dfs(head, root):\n",
    "    if head == None:\n",
    "        return True\n",
    "    if root == None:\n",
    "        return False\n",
    "    if head.val == root.val:\n",
    "        return dfs(head.next, root.left) or dfs(head.next, root.right)\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if dfs(head, root):\n",
    "            return True\n",
    "        if root == None:\n",
    "            return False\n",
    "        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "    def dfs(self,head:ListNode,root:TreeNode):\n",
    "        if not head:\n",
    "            return True\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val != head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next,root.left) or self.dfs(head.next, root.right)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        start = []\n",
    "        def dfs1(node):\n",
    "            nonlocal start\n",
    "            if node: \n",
    "                if node.val == head.val:\n",
    "                    start.append(node)\n",
    "                dfs1(node.left)\n",
    "                dfs1(node.right)\n",
    "        def dfs2(node, head):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not node:\n",
    "                return False\n",
    "            if node and node.val != head.val:\n",
    "                return False\n",
    "            return node and (dfs2(node.right, head.next) or dfs2(node.left, head.next))\n",
    "        dfs1(root)\n",
    "        # print(f'start={start.val}')\n",
    "        return any(dfs2(s, head) for s in start)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,head:ListNode,rt:TreeNode)->bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not rt:\n",
    "            return False\n",
    "        if rt.val!=head.val:\n",
    "            return False\n",
    "        return self.dfs(head.next, rt.left) or self.dfs(head.next, rt.right)\n",
    "\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool: # 找头节点，然后再看是否匹配\n",
    "        if not root:\n",
    "            return False\n",
    "        return self.dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "        # 递归匹配\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 暴力解法，极有可能超时\n",
    "        def search(tree, chain):\n",
    "            if not chain:\n",
    "                return True\n",
    "            if not tree or tree.val != chain.val:\n",
    "                return False\n",
    "            return search(tree.left, chain.next) or search(tree.right, chain.next)\n",
    "        \n",
    "        # 先深搜获得深度，再广搜暴力找答案\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(dfs(node.left), dfs(node.right)) + 1\n",
    "        depth = dfs(root) + 1\n",
    "        # 找找链表的深度\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            depth -= 1\n",
    "            # 没链表深，直接返回\n",
    "            if depth < 0:\n",
    "                return False\n",
    "        # 此时的depth==树深度-链表深度，超过这个深度后，不能出现链表的头节点\n",
    "        \n",
    "\n",
    "        # 开始广搜\n",
    "        q = [root]\n",
    "        for _ in range(depth):\n",
    "            new = []\n",
    "            for node in q:\n",
    "                if search(node, head):\n",
    "                    return True\n",
    "                if node.left:\n",
    "                    new.append(node.left)\n",
    "                if node.right:\n",
    "                    new.append(node.right)\n",
    "            q = new\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 我担心暴力解法，有可能超时\n",
    "        def search(tree, chain):\n",
    "            if not chain:\n",
    "                return True\n",
    "            if not tree or tree.val != chain.val:\n",
    "                return False\n",
    "            return search(tree.left, chain.next) or search(tree.right, chain.next)\n",
    "        \n",
    "        # 先深搜获得深度，再广搜暴力找答案\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(dfs(node.left), dfs(node.right)) + 1\n",
    "        depth = dfs(root) + 1\n",
    "        # 找找链表的深度\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            depth -= 1\n",
    "            # 没链表深，直接返回\n",
    "            if depth < 0:\n",
    "                return False\n",
    "        # 此时的depth==树深度-链表深度，超过这个深度后，不能出现链表的头节点\n",
    "        \n",
    "\n",
    "        # 开始广搜\n",
    "        q = [root]\n",
    "        for _ in range(depth):\n",
    "            new = []\n",
    "            for node in q:\n",
    "                if search(node, head):\n",
    "                    return True\n",
    "                if node.left:\n",
    "                    new.append(node.left)\n",
    "                if node.right:\n",
    "                    new.append(node.right)\n",
    "            q = new\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 暴力解法，极有可能超时\n",
    "        def search(tree, chain):\n",
    "            if not chain:\n",
    "                return True\n",
    "            if not tree or tree.val != chain.val:\n",
    "                return False\n",
    "            return search(tree.left, chain.next) or search(tree.right, chain.next)\n",
    "        \n",
    "        # 先深搜获得深度，再广搜暴力找答案\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(dfs(node.left), dfs(node.right)) + 1\n",
    "        depth = dfs(root) + 1\n",
    "        # 找找链表的深度\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            depth -= 1\n",
    "            # 没链表深，直接返回\n",
    "            if depth < 0:\n",
    "                return False\n",
    "        # 此时的depth==树深度-链表深度，超过这个深度后，不能出现链表的头节点\n",
    "        \n",
    "\n",
    "        # 开始广搜\n",
    "        q = [root]\n",
    "        for _ in range(depth):\n",
    "            new = []\n",
    "            for node in q:\n",
    "                if search(node, head):\n",
    "                    return True\n",
    "                if node.left:\n",
    "                    new.append(node.left)\n",
    "                if node.right:\n",
    "                    new.append(node.right)\n",
    "            q = new\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        All_list = []\n",
    "        def List(h):\n",
    "            if h.left:\n",
    "                List(h.left)\n",
    "            if h.right:\n",
    "                List(h.right)\n",
    "            All_list.append(h)\n",
    "        \n",
    "        List(root)\n",
    "        \n",
    "        def Check(h, r):\n",
    "            if not r:\n",
    "                return False\n",
    "            if h.next == None:\n",
    "                if h.val == r.val:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if h.val == r.val:\n",
    "                    return (Check(h.next, r.left) or Check(h.next, r.right))\n",
    "                else:\n",
    "                    return False\n",
    "                \n",
    "        for i in All_list:\n",
    "            if head.val == i.val:\n",
    "                if Check(head, i):\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not head:\n",
    "           return True\n",
    "        elif not root :\n",
    "            return False\n",
    "        else:\n",
    "            return self.dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "    def dfs(self,head: Optional[ListNode], root: Optional[TreeNode]):\n",
    "        if not head :\n",
    "            return True\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val != head.val:\n",
    "            return False \n",
    "        return self.dfs(head.next , root.left) or self.dfs(head.next,root.right)\n",
    "        \n",
    "\n",
    "    # def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "    #     if not head :return True\n",
    "    #     elif not root :return False\n",
    "       \n",
    "    #     else:\n",
    "    #         return self.dfs(head,root) or self.isSubPath(head , root.left) or self.isSubPath(head ,root.right)\n",
    "\n",
    "    # def dfs(self,head: Optional[ListNode], root: Optional[TreeNode]):\n",
    "    #     if not head :return True\n",
    "    #     if not root :return False\n",
    "    #     if root.val != head.val : return False\n",
    "    #     return self.dfs(head.next , root.left) or self.dfs(head.next , root.right)\n",
    " \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def check(r1, l1):\n",
    "            # base\n",
    "            if not r1 and l1:\n",
    "                return False\n",
    "            \n",
    "            if not r1 and not l1:\n",
    "                return True\n",
    "            \n",
    "            if r1 and not l1:\n",
    "                return True\n",
    "            \n",
    "            if r1.val == l1.val:\n",
    "                if check(r1.left, l1.next):\n",
    "                    return True\n",
    "                if check(r1.right, l1.next):\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "                \n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            \n",
    "            if root.val == head.val:\n",
    "                if check(root, head):\n",
    "                    return True\n",
    "            if dfs(root.left):\n",
    "                return True\n",
    "            if dfs(root.right):\n",
    "                return True\n",
    "            return False\n",
    "            \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # 我担心暴力解法，有可能超时\n",
    "        def search(tree, chain):\n",
    "            if not chain:\n",
    "                return True\n",
    "            if not tree or tree.val != chain.val:\n",
    "                return False\n",
    "            return search(tree.left, chain.next) or search(tree.right, chain.next)\n",
    "        \n",
    "        # 先深搜获得深度，再广搜暴力找答案\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(dfs(node.left), dfs(node.right)) + 1\n",
    "        depth = dfs(root) + 1\n",
    "        # 找找链表的深度\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            depth -= 1\n",
    "            # 没链表深，直接返回\n",
    "            if depth < 0:\n",
    "                return False\n",
    "        # 此时的depth==树深度-链表深度，超过这个深度后，不能出现链表的头节点\n",
    "        \n",
    "\n",
    "        # 开始广搜\n",
    "        q = [root]\n",
    "        for _ in range(depth):\n",
    "            new = []\n",
    "            for node in q:\n",
    "                if search(node, head):\n",
    "                    return True\n",
    "                if node.left:\n",
    "                    new.append(node.left)\n",
    "                if node.right:\n",
    "                    new.append(node.right)\n",
    "            q = new\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def dfs(head: Optional[ListNode], root: Optional[TreeNode]):\n",
    "            if not head :return True\n",
    "            if not root :return False\n",
    "            if root.val != head.val : return False\n",
    "            return dfs(head.next , root.left) or dfs(head.next , root.right)\n",
    "\n",
    "        if not head :return True\n",
    "        elif not root :return False\n",
    "        elif dfs(head,root) : \n",
    "            return True \n",
    "        else:\n",
    "            return self.isSubPath(head , root.left) or self.isSubPath(head ,root.right)\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def dfs(root, node) :\n",
    "            if not node :\n",
    "                return True\n",
    "            if not root :\n",
    "                return False\n",
    "\n",
    "            if root.val != node.val :\n",
    "                return False\n",
    "            \n",
    "            return dfs(root.left, node.next) or dfs(root.right, node.next)\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        return dfs(root, head) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node,heads):\n",
    "            if not heads:\n",
    "                return True\n",
    "            if not node or node.val!=heads.val:\n",
    "                return False\n",
    "            return dfs(node.left,heads.next) or dfs(node.right,heads.next)\n",
    "        if not root:return False\n",
    "        return dfs(root,head) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def path_match(head: Optional[ListNode], root: Optional[TreeNode]):\n",
    "            if not head: return True\n",
    "            if not root: return False\n",
    "            if head.val != root.val:\n",
    "                return False\n",
    "            return path_match(head.next, root.left) or path_match(head.next, root.right)\n",
    "        if not head: return True\n",
    "        if not root: return False\n",
    "        return path_match(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(cur,cur_head):\n",
    "            if cur_head is None:return True \n",
    "            if cur is None:return False \n",
    "            if cur.val!=cur_head.val:\n",
    "                return False \n",
    "            return dfs(cur.left,cur_head.next) or dfs(cur.right,cur_head.next)\n",
    "        # 在所有节点往下走,判断是不是以这个节点为根的子数的链表\n",
    "        # 因为有可能网友有可能网走,所以需要递归判断，用或运算表示\n",
    "        if head is None:return True \n",
    "        if root is None:return False \n",
    "        return dfs(root,head) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def dfs(root, node) :\n",
    "            if not node :\n",
    "                return True\n",
    "            if not root :\n",
    "                return False\n",
    "\n",
    "            if root.val != node.val :\n",
    "                return False\n",
    "            \n",
    "            return dfs(root.left, node.next) or dfs(root.right, node.next)\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        return dfs(root, head) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(head, root):\n",
    "            if head == None:\n",
    "                return True\n",
    "            if root == None:\n",
    "                return False\n",
    "            if head.val == root.val:\n",
    "                return dfs(head.next, root.left) or dfs(head.next, root.right)\n",
    "            return False\n",
    "        \n",
    "        if head == None:\n",
    "            return True\n",
    "        if root == None:\n",
    "            return False\n",
    "\n",
    "        if dfs(head, root):\n",
    "            return True\n",
    "        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if not head :\n",
    "            return True  \n",
    "        if not root:\n",
    "            return False\n",
    "\n",
    "        def isSub(head,root):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not root:\n",
    "                return False\n",
    "            if head.val !=root.val:\n",
    "                return False\n",
    "            return isSub(head.next,root.left) or isSub(head.next,root.right)\n",
    "\n",
    "\n",
    "\n",
    "        return isSub(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right)\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(sub, root):\n",
    "            if not sub: return True\n",
    "            if not root: return False\n",
    "            if root.val != sub.val:\n",
    "                return False\n",
    "            return dfs(sub.next, root.left) or dfs(sub.next, root.right)\n",
    "    \n",
    "        if not root: return False\n",
    "        if dfs(head, root): return True\n",
    "        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "\n",
    "    # def dfs(self, head, root):\n",
    "    #     if head is None:\n",
    "    #         return True\n",
    "    #     elif root is None:\n",
    "    #         return False\n",
    "    #     if root.val == head.val:\n",
    "    #         return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)\n",
    "    #     else:\n",
    "    #         return False\n",
    "\n",
    "\n",
    "    # def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "    #     if root is None:\n",
    "    #         return False\n",
    "    #     return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "\n",
    "        def process(n1, l1):\n",
    "            if l1 is None:\n",
    "                return True\n",
    "            \n",
    "            if n1 is None:\n",
    "                return False\n",
    "            \n",
    "            if n1.val == l1.val:\n",
    "                left = process(n1.left, l1.next)\n",
    "                right = process(n1.right, l1.next)\n",
    "                return left or right\n",
    "  \n",
    "            return False\n",
    "        \n",
    "        return process(root, head) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    tree_paths = []\n",
    "    def traverse_tree(self, root, tmp_path, ll_str):\n",
    "        if not root.left and not root.right:\n",
    "\n",
    "            if ll_str in tmp_path:\n",
    "                return True\n",
    "        if root.left:\n",
    "            if self.traverse_tree(root.left, tmp_path + \",\" + str(root.left.val), ll_str):\n",
    "                return True\n",
    "        if root.right:\n",
    "            if self.traverse_tree(root.right, tmp_path + ',' + str(root.right.val), ll_str):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        if not head or not root:\n",
    "            return False\n",
    "        ll = []\n",
    "        while head:\n",
    "            ll.append(head.val)\n",
    "            head = head.next\n",
    "        ll_str = ','.join([str(x) for x in ll])\n",
    "\n",
    "        return self.traverse_tree(root, str(root.val), ll_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(head, root):\n",
    "            print(\"dfs\")\n",
    "            if head is None:\n",
    "                return True\n",
    "            if root is None:\n",
    "                return False\n",
    "            print(head.val,root.val)\n",
    "            return head.val == root.val and (dfs(head.next, root.left) or dfs(head.next, root.right))\n",
    "        if root is None:\n",
    "            return False\n",
    "        print(\"...\", head.val, root.val)\n",
    "        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:\n",
    "        # def isSub(head, node):\n",
    "        #     if head is None:\n",
    "        #         return True\n",
    "        #     if node is None:\n",
    "        #         return False\n",
    "        #     if head.val != node.val:\n",
    "        #         return False\n",
    "        #     return isSub(head.next, node.left) or isSub(head.next, node.right)\n",
    "        \n",
    "        # if head is None:\n",
    "        #     return True\n",
    "        # if root is None:\n",
    "        #     return False\n",
    "        # return isSub(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n",
    "        def dfs(h, r):\n",
    "            if r == None or h == None:\n",
    "                return False\n",
    "\n",
    "            if h.next == None and h.val == r.val:\n",
    "                return True\n",
    "            \n",
    "            if h.val == r.val:\n",
    "                return dfs(h.next, r.left) or dfs(h.next, r.right)\n",
    "\n",
    "            else:\n",
    "                if head.val == r.val:\n",
    "                    return dfs(head.next, r.left) or dfs(head.next, r.right)\n",
    "                else:\n",
    "                    return dfs(head, r.left) or dfs(head, r.right)\n",
    "        \n",
    "        if head is None:\n",
    "            return True\n",
    "        if root is None:\n",
    "            return False\n",
    "        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        ptn = []\n",
    "        while head:\n",
    "            ptn.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        pi, j = [0] * (m := len(ptn)), 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and ptn[i] != ptn[j]: j = pi[j - 1]\n",
    "            pi[i] = (j := j + 1) if ptn[i] == ptn[j] else j\n",
    "        \n",
    "        @cache\n",
    "        def dfs_kmp(node, j):\n",
    "            if j == m: return True\n",
    "            if node is None: return False\n",
    "\n",
    "            while j > 0 and node.val != ptn[j]: j = pi[j - 1]\n",
    "            delta = int(node.val == ptn[j])\n",
    "            return dfs_kmp(node.left, j + delta) or dfs_kmp(node.right, j + delta)\n",
    "\n",
    "        return dfs_kmp(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        ptn = []\n",
    "        while head:\n",
    "            ptn.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        pi, j = [0] * (m := len(ptn)), 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and ptn[i] != ptn[j]: j = pi[j - 1]\n",
    "            pi[i] = (j := j + 1) if ptn[i] == ptn[j] else j\n",
    "        \n",
    "        @cache\n",
    "        def dfs_kmp(node, j):\n",
    "            if j == m: return True\n",
    "            if node is None: return False\n",
    "\n",
    "            while j > 0 and node.val != ptn[j]: j = pi[j - 1]\n",
    "            delta = int(node.val == ptn[j])\n",
    "            return dfs_kmp(node.left, j + delta) or dfs_kmp(node.right, j + delta)\n",
    "\n",
    "        return dfs_kmp(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:\n",
    "        ptn = []\n",
    "        while head:\n",
    "            ptn.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        pi, j = [0] * (m := len(ptn)), 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and ptn[i] != ptn[j]: j = pi[j - 1]\n",
    "            pi[i] = (j := j + 1) if ptn[i] == ptn[j] else j\n",
    "        \n",
    "        @cache\n",
    "        def dfs_kmp(node, j):\n",
    "            if j == m: return True\n",
    "            if node is None: return False\n",
    "\n",
    "            while j > 0 and node.val != ptn[j]: j = pi[j - 1]\n",
    "            delta = int(node.val == ptn[j])\n",
    "            return dfs_kmp(node.left, j + delta) or dfs_kmp(node.right, j + delta)\n",
    "\n",
    "        return dfs_kmp(root, 0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
